package dp.prevClass.exer02;

import java.util.Scanner;

/**
 * 题目描述：
 * 两个字符串 A 和 B ，长度都为 n 的,每次从字符串A的两个端头（或左或右）取走一个字符，
 * 而B串只能按序从左往右取一个字符。每个字符的ASCII码值为该字符的能量值（区分大小写）。
 * 假设第 i 次取走的字符串A字符为 Ax（A串剩余的左端或右端字符），B字符串取第i个字符为Bi，
 * 将Ax和Bi字符结合后，其能量值为两个字符能量值的乘积；求所有A串中的字符与B串中的字符结合后，
 * 所能获得的最大能量值是多少。
 * 输入要求：
 * 每次输入2行字符串，分别表示字符串A和字符串B；输入保证2个字符串的长度相同。
 * 其中字符串A和B中的字符为大写或小写的英文字符；
 * A、B字符串的长度都不超过10个字符。
 *
 * 输出要求：
 * 输出2个字符串所能得到的最大能量值。
 */
public class Main {
    public static void main(String[] args) {
        // 动态规划思想
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.next();
        String str2 = scanner.next();
        int len = str1.length();
        // dp[i][j]表示从str[i, j]区间的能量最大值
        int[][] dp = new int[len][len];
        // 初始化
        dp[0][len - 1] = 0;
        int sum = 0;
        for (int i = len - 2; i >= 0; i--) {
            sum += str1.charAt(i + 1) * str2.charAt(len - i - 2);
            dp[0][i] = sum;
        }
        sum = 0;
        for (int i = 1; i < len; i++) {
            sum += str1.charAt(i - 1) * str2.charAt(i - 1);
            dp[i][len - 1] = sum;
        }
        // 状态转移
        for (int i = 1; i < len; i++) {
            for (int j = len - 2; j >= 1; j--) {
                if (i <= j) {
                    int gapLen = j - i + 1;
                    int str2StartIndex = (len - gapLen);
                    int mapValue = str2.charAt(str2StartIndex - 1);
                    dp[i][j] = Math.max(dp[i - 1][j] + str1.charAt(i - 1) * mapValue, dp[i][j + 1] + str1.charAt(j + 1) * mapValue);
                }
            }
        }
        // 返回值
        int max = -1;
        for (int i = 0; i < len; i++) {
            max = Math.max(max, dp[i][i] + str2.charAt(str2.length() - 1) * str1.charAt(i));
        }
        System.out.println(max);
    }
}
